Verify that the recurrence relation is satisfied by

\[{u_n} = A{\alpha ^n} + B{\beta ^n},\]

where \(A\) and \(B\) are arbitrary constants.

Solve the recurrence relation

\({u_{n + 2}} - 2{u_{n + 1}} + 5{u_n} = 0\) given that \({u_0} = 0\) and \({u_1} = 4\).

Show that \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = {\text{gcd}}\left( {k - 1,\,2} \right)\), where \(k \in {\mathbb{Z}^ + },\,k > 1\).

State the value of \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right)\) for odd positive integers \(k\).

State the value of \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right)\) for even positive integers \(k\).

Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for \(G\).

By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s algorithm to find a lower bound for the travelling salesman problem for \(G\).

Draw the weighted graph \(H\).

Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.

By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.

Use the recurrence relation to find \({u_2}\).

Find an expression for \({u_n}\) in terms of \(n\).

A second recurrence relation, where \({v_1} = {u_1}\) and \({v_2} = {u_2}\), is given by \({v_{n + 1}} + 2{v_n} + {v_{n - 1}} = 0,{\text{ }}n \ge 2\).

Find an expression for \({v_n}\) in terms of \(n\).

Draw the complete bipartite graph \({\kappa _{3,3}}\).

Prove that \({\kappa _{3,3}}\) is not planar.

A connected graph \(G\) has \(v\) vertices. Prove, using Euler’s relation, that a spanning tree for \(G\) has \(v - 1\) edges.

If an edge \(E\) is chosen at random from the edges of \({\kappa _n}\), show that the probability that \(E\) belongs to \(T\) is equal to \(\frac{2}{n}\).

(i)     Draw the graph \({\kappa _4}\) including the weights of all the edges.

(ii)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a Hamiltonian cycle.

(iii)     Hence, find an upper bound to the travelling salesman problem for this weighted graph.

Consider the graph \({\kappa _5}\). Use the deleted vertex algorithm, with \({{\text{A}}_5}\) as the deleted vertex, to find a lower bound to the travelling salesman problem for this weighted graph.

(i)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a Hamiltonian cycle.

(ii)    Hence find and simplify an expression in \(n\), for an upper bound to the travelling salesman problem for this weighted graph.

By splitting the weight of the edge \({{\text{A}}_i}{{\text{A}}_j}\) into two parts or otherwise, show that all Hamiltonian cycles of \({\kappa _n}\) have the same total weight, equal to the answer found in (c)(ii).

(i)     By converting the base 7 number to base 10, find the value of \(x\), in base 10.

(ii)     Express \(x\) as a base 5 number.

Let \(y\) be the base 9 number \({({a_n}{a_{n - 1}} \ldots {a_1}{a_0})_9}\). Show that \(y\) is exactly divisible by 8 if and only if the sum of its digits, \(\sum\limits_{i = 0}^n {{a_i}} \), is also exactly divisible by 8.

Using the method from part (b), find the unit digit when the base 9 number \({(321321321)_9}\) is written as a base 8 number.

With reference to the integers 5, 8 and 3, state why the Chinese remainder theorem guarantees a unique solution modulo 120 to this system of linear congruences.

Hence or otherwise, find the general solution to the above system of linear congruences.

a graph cannot exist with a degree sequence of \(1,{\text{ }}2,{\text{ }}3,{\text{ }}4,{\text{ }}5,{\text{ }}6,{\text{ }}7,{\text{ }}8,{\text{ }}9\);

a simple, connected, planar graph cannot exist with a degree sequence of \(4,{\text{ }}4,{\text{ }}4,{\text{ }}4,{\text{ }}5,{\text{ }}5\);

a tree cannot exist with a degree sequence of \(1,{\text{ }}1,{\text{ }}2,{\text{ }}2,{\text{ }}3,{\text{ }}3\).

The distances by road, in kilometres, between towns in Switzerland are shown in the following table.

A cable television company wishes to connect the six towns placing cables along the road system.

Use Kruskal’s algorithm to find the minimum length of cable needed to connect the six towns.

Visitors to Switzerland can visit some principal locations for tourism by using a network of scenic railways as represented by the following graph:

(i)     State whether the graph has any Hamiltonian paths or Hamiltonian cycles, justifying your answers.

(ii)     State whether the graph has any Eulerian trails or Eulerian circuits, justifying your answers.

(iii)     The tourist board would like to make it possible to arrive in Geneva, travel all the available scenic railways, exactly once, and depart from Zurich. Find which locations would need to be connected by a further scenic railway in order to make this possible.

Find the values of \({u_1},{\text{ }}{u_2},{\text{ }}{u_3}\).

Show that \({u_{n + 2}} = {u_{n + 1}} + {u_n}\).

(i)     Write down the auxiliary equation for this recurrence relation.

(ii)     Hence find the solution to this recurrence relation, giving your answer in the form \({u_n} = A{\alpha ^n} + B{\beta ^n}\) where \(\alpha \) and \(\beta \) are to be determined exactly in surd form and \(\alpha  > \beta \). The constants \(A\) and \(B\) do not have to be found at this stage.

(i)     Given that \(A = \frac{1}{{\sqrt 5 }}\left( {\frac{{1 + \sqrt 5 }}{2}} \right)\), use the value of \({u_0}\) to determine \(B\).

(ii)     Hence find the explicit formula for \({u_n}\).

Find the value of \({u_{20}}\).

Find the smallest value of \(n\) for which \({u_n} > 100\,000\).

Use the result \(2003 = 6 \times 333 + 5\) and Fermat’s little theorem to show that \({2^{2003}} \equiv 4(\bmod 7)\) .

Find \({2^{2003}}(\bmod 11)\) and \({2^{2003}}(\bmod 13)\).

Use the Chinese remainder theorem, or otherwise, to evaluate \({2^{2003}}(\bmod 1001)\), noting that \(1001 = 7 \times 11 \times 13\).

Using the Euclidean algorithm, find h .

Hence find integers A and B such that 861A + 957B = h .

Using part (b), solve \(287w \equiv 2(\bmod 319\)) , where \(w \in \mathbb{N},{\text{ }}w < 319\) .

Find the general solution to the diophantine equation \(861x + 957y = 6\) .

State what feature of G ensures that G has an Eulerian trail.

State what feature of G ensures that G does not have an Eulerian circuit.

Write down an Eulerian trail in G.

State the Chinese postman problem.

Starting and finishing at B, find a solution to the Chinese postman problem for G.

Calculate the total weight of the solution.

Show that the number of edges in \(G'\), the complement of \(G\), is \(\frac{1}{2}{v^2} - \frac{1}{2}v - e\).

show that the sum of the number of faces in \(G\) and the number of faces in \(G'\) is independent of \(e\);

show that \({v^2} - 13v + 24 \leqslant 0\) and hence determine the maximum possible value of \(v\).

Write down the auxiliary equation and use it to find an expression for \({f_n}\) in terms of \(n\).

It is known that \({\alpha ^2} = \alpha  + 1\) where \(\alpha  = \frac{{1 + \sqrt 5 }}{2}\).

For integers \(n\) ≥ 3, use strong induction on the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) to prove that \({f_n} > {\alpha ^{n - 2}}\).

Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315.

Hence state the number of solutions to the diophantine equation 7854x + 3315y = 41 and justify your answer.

Find an expression for \({u_n}\) in terms of \(n\).

For every prime number \(p > 3\), show that \(p|{u_{p - 1}}\).

Convert the decimal number 1071 to base 12.

Write the decimal number 1071 as a product of its prime factors.

Using your answers to part (a) and (b), prove that there is only one possible value for \(b\) and state this value.

Hence state the value of \(a\).

Use the Euclidean algorithm to find the greatest common divisor of 264 and 1365.

Hence, or otherwise, find the general solution of the Diophantine equation

\[264x - 1365y = 3.\]

Hence find the general solution of the Diophantine equation

\[264x - 1365y = 6.\]

By expressing each of 264 and 1365 as a product of its prime factors, determine the lowest common multiple of 264 and 1365.

Prove that a graph containing a triangle cannot be bipartite.

Prove that the number of edges in a bipartite graph with n vertices is less than or equal to \(\frac{{{n^2}}}{4}\).

Show that when p = 2 , N is even if and only if its least significant digit, \({a_0}\) , is 0.

Show that when p = 3 , N is even if and only if the sum of its digits is even.

Given a sequence of non negative integers \(\{ {a_r}\} \) show that

(i)     \(\sum\limits_{r = 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) = \sum\limits_{r = 0}^n {{a_r}(\bmod x)} } \) where \(x \in \{ 2,{\text{ }}3,{\text{ }}4 \ldots \} \).

(ii)     \(\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} } \).

Hence determine whether the base \(3\) number \(22010112200201\) is divisible by \(8\).

State Fermat’s little theorem.

Use Fermat’s little theorem to show that \(x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)\).

Hence solve the linear congruence \(5x \equiv 7\left( {{\text{mod}}\,13} \right)\).

Show that \(G\) is bipartite.

State which two vertices should be joined to make \(G\) equivalent to \({K_{3,{\text{ }}3}}\).

In a planar graph the degree of a face is defined as the number of edges adjacent to that face.

(i)     Write down the degree of each of the four faces of \(G\).

(ii)     Explain why the sum of the degrees of all the faces is twice the number of edges.

\(H\) is a simple connected planar bipartite graph with \(e\) edges, \(f\) faces, \(v\) vertices and \(v \ge 3\).

Explain why there can be no face in \(H\) of degree

(i)     one;

(ii)     two;

(iii)     three.

Hence prove that for \(H\)

(i)     \(e \ge 2f\);

(ii)     \(e \le 2v - 4\).

Hence prove that \({K_{3,{\text{ }}3}}\) is not planar.

Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where \(p,{\text{ }}q \in \mathbb{Z}\).

Find the least positive solution of \(123x \equiv 1(\bmod 2347)\) .

Find the general solution of \(123z \equiv 5(\bmod 2347)\) .

State the solution set of \(123y \equiv 1(\bmod 2346)\) .

The planar graph G and its complement \(G'\) are both simple and connected.

Given that G has 6 vertices and 10 edges, show that \(G'\) is a tree.

Draw \({K_{2,{\text{ }}2}}\) as a planar graph.

Draw a spanning tree for \({K_{2,{\text{ }}2}}\).

Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).

Show that the complement of any complete bipartite graph does not possess a spanning tree.

(i)     Given that \({(43)_n} \times {(56)_n} = {(3112)_n}\), show that \(3{n^3} - 19{n^2} - 38n - 16 = 0\).

(ii)     Hence determine the value of \(n\).

Determine the set of values of \(n\) satisfying \({(13)_n} \times {(21)_n} = {(273)_n}\).

Show that there are no possible values of \(n\) satisfying \({(32)_n} \times {(61)_n} = {(1839)_n}\).

Solve the recurrence relation \({v_n} + 4{v_{n - 1}} + 4{v_{n - 2}} = 0\) where \({v_1} = 0,{\text{ }}{v_2} = 1\).

Use strong induction to prove that the solution to the recurrence relation \({u_n} - 4{u_{n - 1}} + 4{u_{n - 2}} = 0\) where \({u_1} = 0,{\text{ }}{u_2} = 1\) is given by \({u_n} = {2^{n - 2}}(n - 1)\).

Find a simplified expression for \({u_n} + {v_n}\) given that,

(i)     \(n\) is even.

(ii)     \(n\) is odd.

Use the Euclidean algorithm to show that 1463 and 389 are relatively prime.

Find positive integers \(a\) and \(b\) such that \[1463a - 389b = 1\].

In the context of graph theory, explain briefly what is meant by a circuit;

In the context of graph theory, explain briefly what is meant by an Eulerian circuit.

The graph \(G\) has six vertices and an Eulerian circuit. Determine whether or not its complement \(G'\) can have an Eulerian circuit.

Find an example of a graph \(H\), with five vertices, such that \(H\) and its complement \(H'\) both have an Eulerian trail but neither has an Eulerian circuit. Draw \(H\) and \(H'\) as your solution.

By writing down an appropriate polynomial equation, determine the value of n.

Rewrite the above equation with numbers in base 7.

Find the values of \(f(3)\), \(f(4)\) and \(f(5)\).

Use the Euclidean algorithm to find

(i)     \(\gcd \left( {f(3),{\text{ }}f(4)} \right)\);

(ii)     \(\gcd \left( {f(4),{\text{ }}f(5)} \right)\).

Explain why \(f(n)\) is always exactly divisible by \(5\).

By factorizing \(f(n)\) explain why it is always exactly divisible by \(6\).

Determine the values of \(n\) for which \(f(n)\) is exactly divisible by \(60\).

(i)     One version of Fermat’s little theorem states that, under certain conditions,

\[{a^{p - 1}} \equiv 1(\bmod p).\]

Show that this result is not valid when a = 4, p = 9 and state which

condition is not satisfied.

(ii)     Given that \({5^{64}} \equiv n(\bmod 7)\), where \(0 \leqslant n \leqslant 6\), find the value of n.

Find the general solution to the simultaneous congruences

\[x \equiv 3(\bmod 4)\]

\[3x \equiv 2(\bmod 5).\]

(a)     (i)     Write down the general solution of the recurrence relation \({u_n} + 2{u_{n - 1}} = 0,{\text{ }}n \geqslant 1\).

          (ii)     Find a particular solution of the recurrence relation \({u_n} + 2{u_{n - 1}} = 3n - 2,{\text{ }}n \geqslant 1\), in the

          form \({u_n} = An + B\), where \(A,{\text{ }}B \in \mathbb{Z}\).

          (iii)     Hence, find the solution to \({u_n} + 2{u_{n - 1}} = 3n - 2,{\text{ }}n \geqslant 1\) where \({u_1} = 7\).

(b)     Find the solution of the recurrence relation \({u_n} = 2{u_{n - 1}} - 2{u_{n - 2}},{\text{ }}n \geqslant 2\), where \({u_0} = 2,{\text{ }}{u_1} = 2\). Express your solution in the form \({2^{f(n)}}\cos \left( {g(n)\pi } \right)\), where the functions f and g map \(\mathbb{N}\) to \(\mathbb{R}\).

Use the above result to show that if p is prime then \({a^p} \equiv a(\bmod p)\) where a is any positive integer.

Show that \({2^{341}} \equiv 2(\bmod 341)\).

(i)     State the converse of the result in part (a).

(ii)     Show that this converse is not true.

Draw the graph \(K\).

Starting from customer D, use the nearest-neighbour algorithm, to determine an upper bound to the travelling salesman problem for K.

By removing customer A, use the method of vertex deletion, to determine a lower bound to the travelling salesman problem for K.

(i)     Given that \(a \equiv d(\bmod n)\) and \(b \equiv c(\bmod n)\) prove that

\[(a + b) \equiv (c + d)(\bmod n){\text{ .}}\]

(ii)     Hence solve the system

\[\left\{ {\begin{array}{*{20}{r}}
  {2x + 5y \equiv 1(\bmod 6)} \\
  {x + y \equiv 5(\bmod 6)}
\end{array}} \right.\]

Show that \({x^{97}} - x + 1 \equiv 0(\bmod 97)\) has no solution.

The sequence \(\{ {u_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation \({u_{n + 1}} = 7{u_n} - 6\).

Given that \({u_0} = 5\), find an expression for \({u_n}\) in terms of \(n\).

The sequence \(\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation \({v_{n + 2}} = 10{v_{n + 1}} + 11{v_n}\).

Given that \({v_0} = 4\) and \({v_1} = 44\), find an expression for \({v_n}\) in terms of \(n\).

The sequence \(\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation \({v_{n + 2}} = 10{v_{n + 1}} + 11{v_n}\).

Show that \({v_n} - {u_n} \equiv 15(\bmod 16),{\text{ }}n \in \mathbb{N}\).

(i)     Explain briefly why the graph contains an Eulerian trail but not an Eulerian circuit.

(ii)     Write down an Eulerian trail.

(i)     Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D.

(ii)     State the minimum total weight.

(a)     Use the Euclidean algorithm to find gcd(\(12\,306\), 2976) .

(b)     Hence give the general solution to the diophantine equation \(12\,306\)x + 2976y = 996 .

Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.

(i)     Find the general solution to the diophantine equation \(56x + 315y = 21\).

(ii)     Hence or otherwise find the smallest positive solution to the congruence \(315x \equiv 21\) (modulo 56) .

Given that a , \(b \in \mathbb{N}\) and \(c \in {\mathbb{Z}^ + }\), show that if \(a \equiv 1(\bmod c)\) , then \(ab \equiv b(\bmod c)\) .

Using mathematical induction, show that \({9^n} \equiv 1(\bmod 4)\) , for \(n \in \mathbb{N}\) .

The positive integer M is expressed in base 9. Show that M is divisible by 4 if the sum of its digits is divisible by 4.

Two mathematicians are planning their wedding celebration and are trying to arrange the seating plan for the guests. The only restriction is that all tables must seat the same number of guests and each table must have more than one guest. There are fewer than 350 guests, but they have forgotten the exact number. However they remember that when they try to seat them with two at each table there is one guest left over. The same happens with tables of 3, 4, 5 and 6 guests. When there were 7 guests per table there were none left over. Find the number of guests.

Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is divisible by 9.

The representation of the positive integer N in base p is denoted by \({(N)_p}\) .

If \({({5^{{{(126)}_7}}})_7} = {({a_n}{a_{n - 1}} \ldots {a_1}{a_0})_7}\) , find \({a_0}\) .

The positive integer N is expressed in base 9 as \({({a_n}{a_{n - 1}} \ldots {a_0})_9}\).

(a)     Show that N is divisible by 3 if the least significant digit, \({a_0}\), is divisible by 3.

(b)     Show that N is divisible by 2 if the sum of its digits is even.

(c)     Without using a conversion to base 10, determine whether or not \({(464860583)_9}\) is divisible by 12.

Explaining your method fully, determine whether or not 1189 is a prime number.

(i)     State the fundamental theorem of arithmetic.

(ii)     The positive integers M and N have greatest common divisor G and least common multiple L . Show that GL = MN .

State the value of \({u_1}\).

Show that \({u_n}\) satisfies the recurrence relation

\[{u_n} = \frac{1}{4}{u_{n - 1}} + \frac{1}{4}.\]

Solve this recurrence relation to find the probability that Andy wins the \({n^{{\text{th}}}}\) game.

After they have played many games, Pat comes to watch. Use your answer from part (c) to estimate the probability that Andy will win the game they are playing when Pat arrives.

Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.

Seventeen people attend a meeting.

Each person shakes hands with at least one other person and no-one shakes hands with

the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.

Explain why each person cannot have shaken hands with exactly nine other people.

A graph has n vertices with degrees 1, 2, 3, …, n. Prove that \(n \equiv 0(\bmod 4)\) or \(n \equiv 3(\bmod 4)\).

Let G be a simple graph with n vertices, \(n \geqslant 2\). Prove, by contradiction, that at least two of the vertices of G must have the same degree.

Use the Euclidean algorithm to find \(\gcd (752,{\text{ }}352)\).

A farmer spends £8128 buying cows of two different breeds, A and B, for her farm. A cow of breed A costs £752 and a cow of breed B costs £352.

(i)     Set up a diophantine equation to show this.

(ii)     Using your working from part (a), find the general solution to this equation.

(iii)     Hence find the number of cows of each breed bought by the farmer.

Show that graph \(G\) is Hamiltonian. Find the total number of Hamiltonian cycles in \(G\), giving reasons for your answer.

State an upper bound for the travelling salesman problem for graph \(G\).

Hence find a lower bound for the travelling salesman problem for \(G\).

Show that the lower bound found in (d) cannot be the length of an optimal solution for the travelling salesman problem for the graph \(G\).

Define what is meant by the statement \(x \equiv y(\bmod n){\text{ where }}x{\text{, }}y{\text{, }}n \in {\mathbb{Z}^ + }\) .

Hence prove that if \(x \equiv y(\bmod n)\) then \({x^2} \equiv {y^2}(\bmod n)\) .

Determine whether or not \({x^2} \equiv {y^2}(\bmod n)\) implies that \(x \equiv y(\bmod n)\) .

Convert the decimal number 51966 to base 16.

(i)     Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and 612.

(ii)     Find integers p and q such that 901p + 612q = d .

(iii)     Find the least possible positive integers s and t such that 901s − 612t = 85.

In each of the following cases find the solutions, if any, of the given linear congruence.

(i)     \(9x \equiv 3(\bmod 18)\)

(ii)     \(9x \equiv 3(\bmod 15)\)

Given that \(a,{\text{ }}b,{\text{ }}c,{\text{ }}d \in \mathbb{Z}\), show that

\[(a - b)(a - c)(a - d)(b - c)(b - d)(c - d) \equiv 0(\bmod 3).\]

The sequence \(\{ {u_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({u_{n + 2}} = 5{u_{n + 1}} - 6{u_n}\) .

Given that \({u_1} = {u_2} = 3\) , obtain an expression for \({u_n}\) in terms of n .

The sequence \(\{ {v_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({v_{n + 2}} = 4{v_{n + 1}} - 4{v_n}\) .

Given that \({v_1} = 2\) and \({v_2} = 12\) , use the principle of strong mathematical induction to show that \({v_n} = {2^n}(2n - 1)\) .

State the Fundamental theorem of arithmetic for positive whole numbers greater than \(1\).

Use the Fundamental theorem of arithmetic, applied to \(5577\) and \(99\,099\), to calculate \(\gcd (5577,{\text{ }}99\,099)\) and \({\text{lcm}}(5577,{\text{ }}99\,099)\), expressing each of your answers as a product of prime numbers.

Prove that \(\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m\) for all \(n,{\text{ }}m \in {\mathbb{Z}^ + }\).

The following figure shows the floor plan of a museum.

(a)     (i)     Draw a graph G that represents the plan of the museum where each exhibition room is represented by a vertex labelled with the exhibition room number and each door between exhibition rooms is represented by an edge. Do not consider the entrance foyer as a museum exhibition room.

(ii)     Write down the degrees of the vertices that represent each exhibition room.

(iii)     Virginia enters the museum through the entrance foyer. Use your answers to (i) and (ii) to justify why it is possible for her to visit the thirteen exhibition rooms going through each internal doorway exactly once.

(b)     Let G and H be two graphs whose adjacency matrices are represented below.

Using the adjacency matrices,

(i)     find the number of edges of each graph;

(ii)     show that exactly one of the graphs has a Eulerian trail;

(iii)     show that neither of the graphs has a Eulerian circuit.

Show that \(30\) is a factor of \({n^5} - n\) for all \(n \in \mathbb{N}\).

(i)     Show that \({3^{{3^m}}} \equiv 3({\text{mod}}4)\) for all \(m \in \mathbb{N}\).

(ii)     Hence show that there is exactly one pair \((m,{\text{ }}n)\) where \(m,{\text{ }}n \in \mathbb{N}\), satisfying the equation \({3^{{3^m}}} = {2^{{2^n}}} + {5^2}\).

(a)     Draw a spanning tree for

          (i)     the complete graph, \({K_4}\);

          (ii)     the complete bipartite graph, \({K_{4,4}}\).

(b)     Prove that a simple connected graph with n vertices, where \(n > 1\), must have two vertices

of the same degree.

(c)     Prove that every simple connected graph has at least one spanning tree.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for \(G\).

By first removing A , use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for \(G\).

Use Dijkstra’s algorithm to find the cheapest route between \(A\) and \(J\), and state its cost.

For the remainder of the question you may find the cheapest route between any two towns by inspection.

It is given that the total cost of travelling on all the roads without repeating any is \(\$ 139\).

A tourist decides to go over all the roads at least once, starting and finishing at town \(A\).

Find the lowest possible cost of his journey, stating clearly which roads need to be travelled more than once. You must fully justify your answer.

Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.

Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .

An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence has first term 7 and common difference 5. Find the set of all numbers which are members of both sequences.

Using the Euclidean algorithm, show that \(\gcd (99,{\text{ }}332) = 1\).

(i)     Find the general solution to the diophantine equation \(332x - 99y = 1\).

(ii)     Hence, or otherwise, find the smallest positive integer satisfying the congruence \(17z \equiv 1(\bmod 57)\).

Solve, by any method, the following system of linear congruences

     \(x \equiv 9(\bmod 11)\)

     \(x \equiv 1(\bmod 5)\)

Find the remainder when \({41^{82}}\) is divided by 11.

Using your answers to parts (a) and (b) find the remainder when \({41^{82}}\) is divided by \(55\).

Consider an integer \(a\) with \((n + 1)\) digits written as \(a = {10^n}{a_n} + {10^{n - 1}}{a_{n - 1}} +  \ldots  + 10{a_1} + {a_0}\), where \(0 \leqslant {a_i} \leqslant 9\) for \(0 \leqslant i \leqslant n\), and \({a_n} \ne 0\).

(a)     Show that \(a \equiv ({a_n} + {a_{n - 1}} +  \ldots  + {a_0}) ({\text{mod9}})\).

(b)     Hence find all pairs of values of the single digits \(x\) and \(y\) such that the number \(a = 476x212y\) is a multiple of \(45\).

(c)     (i)     If \(b = 34\,390\) in base 10, show that \(b\) is \(52\,151\) written in base 9.

(ii)     Hence find \({b^2}\) in base 9, by performing all the calculations without changing base.

(a)     Find the general solution for the following system of congruences.

     \(N \equiv 3(\bmod 11)\)

     \(N \equiv 4(\bmod 9)\)

     \(N \equiv 0(\bmod 7)\)

(b)     Find all values of N such that \(2000 \leqslant N \leqslant 4000\).

Anna is playing with some cars and divides them into three sets of equal size. However, when she tries to divide them into five sets of equal size, there are four left over. Given that she has fewer than 50 cars, what are the possible numbers of cars she can have?

Consider the integers \(a = 871\) and \(b= 1157\), given in base \(10\).

(i)     Express \(a\) and \(b\) in base \(13\).

(ii)     Hence show that \({\text{gcd}}(a,{\text{ }}b) = 13\).

A list \(L\) contains \(n+ 1\) distinct positive integers. Prove that at least two members of \(L\)leave the same remainder on division by \(n\).

Consider the simultaneous equations

     \(4x + y + 5z = a\)

     \(2x + z = b\)

     \(3x + 2y + 4z = c\)

where \(x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}\).

(i)     Show that 7 divides \(2a + b - c\).

(ii)     Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.

Consider the set \(P\) of numbers of the form \({n^2} - n + 41,{\text{ }}n \in \mathbb{N}\).

(i)     Prove that all elements of P are odd.

(ii)     List the first six elements of P for n = 0, 1, 2, 3, 4, 5.

(iii)     Show that not all elements of P are prime.

One version of Fermat’s little theorem states that, under certain conditions, \({a^{p - 1}} \equiv 1(\bmod p)\) .

(i)     Show that this result is not true when a = 2, p = 9 and state which of the conditions is not satisfied.

(ii)     Find the smallest positive value of k satisfying the congruence \({2^{45}} \equiv k(\bmod 9)\) .

Find all the integers between 100 and 200 satisfying the simultaneous congruences \(3x \equiv 4(\bmod 5)\) and \(5x \equiv 6(\bmod 7)\) .

(i)     Show that \(2e \ge 3f{\text{ if }}v > 2\).

(ii)     Hence show that \({K_5}\), the complete graph on five vertices, is not planar.

(i)     State the handshaking lemma.

(ii)     Determine the value of \(f\), if each vertex has degree \(2\).

Draw an example of a simple connected planar graph on \(6\) vertices each of degree \(3\).

The weights of the edges of a graph \(H\) are given in the following table.

(i)     Draw the weighted graph \(H\).

(ii)     Use Kruskal’s algorithm to find the minimum spanning tree of \(H\). Your solution should indicate the order in which the edges are added.

(iii)     State the weight of the minimum spanning tree.

Consider the following weighted graph.

(i) Write down a solution to the Chinese postman problem for this graph.

(ii) Calculate the total weight of the solution.

(i)     State the travelling salesman problem.

(ii)     Explain why there is no solution to the travelling salesman problem for this graph.

Show that there are exactly two solutions to the equation \(1982 = 36a + 74b\), with \(a,{\text{ }}b \in \mathbb{N}\).

Hence, or otherwise, find the remainder when \({1982^{1982}}\) is divided by \(37\).

(a)     Using Fermat’s little theorem, show that, in base 10, the last digit of n is always equal to the last digit of \({n^5}\) .

(b)     Show that this result is also true in base 30.

Write 57128 as a product of primes.

Prove that \(\left. {22} \right|{5^{11}} + {17^{11}}\).

(i)     Determine if any Hamiltonian cycles exist in G . If so, write one down.

Otherwise, explain what feature of G makes it impossible for a Hamiltonian cycle to exist.

(ii)     Determine if any Eulerian circuits exist in G . If so, write one down.

Otherwise, explain what feature of G makes it impossible for an Eulerian circuit to exist.

The following diagram shows a weighted graph.

(a)     Use Kruskal’s algorithm to find a minimum spanning tree, clearly showing the order in which the edges are added.

(b)     Sketch the minimum spanning tree found, and write down its weight.

(a)     (i)     Show that Euler’s relation \(f - e + v = 2\) is valid for a spanning tree of G.

  (ii)     By considering the effect of adding an edge on the values of  f,  e and v show that Euler’s relation remains true.

(b)     Show that K₅ is not planar.

(a)     Write down Fermat’s little theorem.

(b)     In base 5 the representation of a natural number X is \({\left( {k00013(5 - k)} \right)_5}\).

This means that \(X = k \times {5^6} + 1 \times {5^2} + 3 \times 5 + (5 - k)\).

In base 7 the representation of X is \({({a_n}{a_{n - 1}} \ldots {a_2}{a_1}{a_0})_7}\).

Find \({a_0}\).

(c)     Given that k = 2, find X in base 7.

(a)     Show that, for a connected planar graph,

\[v + f - e = 2.\]

(b)     Assuming that \(v \geqslant 3\), explain why, for a simple connected planar graph, \(3f \leqslant 2e\) and hence deduce that \(e \leqslant 3v - 6\).

(c)     The graph G and its complement \({G'}\) are simple connected graphs, each having 12 vertices. Show that \({G}\) and \({G'}\) cannot both be planar.

State Fermat’s little theorem.

Show that \(\sum\limits_{k = 1}^p {{k^p} \equiv 0(\bmod p)} \).

Given that \(\sum\limits_{k = 1}^p {{k^{p - 1}} \equiv n(\bmod p)} \) where \(0 \leqslant n \leqslant p - 1\), find the value of n.

(a)     Use the Euclidean algorithm to find the gcd of 324 and 129.

(b)     Hence show that \(324x + 129y = 12\) has a solution and find both a particular solution and the general solution.

(c)     Show that there are no integers x and y such that \(82x + 140y = 3\) .

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for G .

(i)     Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph obtained by removing the vertex A from G .

(ii)     Hence use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for G .

Draw the graph G .

What information about G is contained in the diagonal elements of M\(^2\) ?

List the trails of length 4 starting at A and ending at C.

Show that a graph is bipartite if and only if it contains only cycles of even length.

The weighted graph H is shown below.

Use Kruskal’s Algorithm, indicating the order in which the edges are added, to find and draw the minimum spanning tree for H.

(i)     A tree has v vertices. State the number of edges in the tree, justifying your answer.

(ii)     We will call a graph with v vertices a “forest” if it consists of c components each of which is a tree. 

Here is an example of a forest with 4 components.

How many edges will a forest with v vertices and c components have?

Draw G in a planar form.

Giving a reason, determine the maximum number of edges that could be added to G while keeping the graph both simple and planar.

List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two cycles each of which is the reverse of the other are to be regarded as identical. Hence determine the Hamiltonian cycle of least weight.

By first finding a minimum spanning tree on the subgraph of H formed by deleting vertex A and all edges connected to A, find a lower bound for this problem.

Find the total weight of the cycle ADCBEA.

What do you conclude from your results?

Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F. The possible roads and the costs of building them are shown in the graph below. Each vertex represents a town, each edge represents a road and the weight of each edge is the cost of building that road. He needs to design the lowest cost road system that will connect the six towns.

(a)     Name an algorithm which will allow Sameer to find the lowest cost road system.

(b)     Find the lowest cost road system and state the cost of building it. Show clearly the steps of the algorithm.

Draw \({\kappa _{3,\,3}}\).

Show that \({\kappa _{3,\,3}}\) has a Hamiltonian cycle.

Draw \({\kappa _{3,\,2}}\) and explain why it does not have a Hamiltonian cycle.

In the context of graph theory, state the handshaking lemma.

Hence show that a graph G with degree sequence 2, 3, 3, 4, 4, 5 cannot exist.

Let T be a tree with \(v\) where \(v\) ≥ 2.

Use the handshaking lemma to prove that T has at least two vertices of degree one.

Draw the complement of the following graph as a planar graph.

A simple graph G has v vertices and e edges. The complement \(G'\) of G has \({e'}\) edges.

(i)     Prove that \(e \leqslant \frac{1}{2}v(v - 1)\) .

(ii)     Find an expression for \(e + e'\) in terms of v .

(iii)     Given that \({G'}\) is isomorphic to G , prove that v is of the form 4n or 4n + 1 for \(n \in {\mathbb{Z}^ + }\) .

(iv)     Prove that there is a unique simple graph with 4 vertices which is isomorphic to its complement.

(v)     Prove that if \(v \geqslant 11\) , then G and \({G'}\) cannot both be planar.

(a)     A connected planar graph G has e edges and v vertices.

(i)     Prove that \(e \geqslant v - 1\).

(ii)     Prove that e = v −1 if and only if G is a tree.

(b)     A tree has k vertices of degree 1, two of degree 2, one of degree 3 and one of degree 4. Determine k and hence draw a tree that satisfies these conditions.

(c)     The graph H has the adjacency table given below.

\[\left( {\begin{array}{*{20}{c}}
  0&1&1&0&0&0 \\
  1&0&0&1&1&0 \\
  1&0&0&0&1&1 \\
  0&1&0&0&0&0 \\
  0&1&1&0&0&0 \\
  0&0&1&0&0&0
\end{array}} \right)\]

(i)     Explain why H cannot be a tree.

(ii)     Draw the graph of H .

(d)     Prove that a tree is a bipartite graph.

(a)     (i)     What feature of the graph enables you to deduce that G contains an Eulerian circuit?

  (ii)     Find an Eulerian circuit.

(c)     Use Kruskal’s Algorithm to find the minimum spanning tree for G , showing the order in which the edges are added.

Draw the graph G as a planar graph.

Giving a reason, state whether or not G is

(i)     simple;

(ii)     connected;

(iii)     bipartite.

Explain what feature of G enables you to state that it has an Eulerian trail and write down a trail.

Explain what feature of G enables you to state it does not have an Eulerian circuit.

Find the maximum number of edges that can be added to the graph G (not including any loops or further multiple edges) whilst still keeping it planar.

(i)     A graph is simple, planar and connected. Write down the inequality connecting v and e, and give the condition on v for this inequality to hold.

(ii)     Sketch a simple, connected, planar graph with v = 2 where the inequality from part (b)(i) is not true.

(iii)     Sketch a simple, connected, planar graph with v =1 where the inequality from part (b)(i) is not true.

(iv)     Given a connected, planar graph with v vertices, \({v^2}\) edges and 8 faces, find v. Sketch a graph that fulfils all of these conditions.

The table below shows the distances between towns A, B, C, D and E.

(i)     Draw the graph, in its planar form, that is represented by the table.

(ii)     Write down with reasons whether or not it is possible to find an Eulerian trail in this graph.

(iii)     Solve the Chinese postman problem with reference to this graph if A is to be the starting and finishing point. Write down the walk and determine the length of the walk.

Show that a graph cannot have exactly one vertex of odd degree.

A graph G with vertices A, B, C, D, E has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}
  {}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
  {\text{A}}& - &{12}&{10}&{17}&{19} \\
  {\text{B}}&{12}& - &{13}&{20}&{11} \\
  {\text{C}}&{10}&{13}& - &{16}&{14} \\
  {\text{D}}&{17}&{20}&{16}& - &{15} \\
  {\text{E}}&{19}&{11}&{14}&{15}& -  
\end{array}\]

(a)     (i)     Use Kruskal’s algorithm to find and draw the minimum spanning tree for G.

  (ii)     The graph H is formed from G by removing the vertex D and all the edges connected to D. Draw the minimum spanning tree for H and use it to find a lower bound for the travelling salesman problem for G.

(b)     Show that 80 is an upper bound for this travelling salesman problem.

Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph and state its length.

Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted graph and state its length.

The adjacency table of the graph G , with vertices P, Q, R, S, T is given by:

(a)     Draw the graph G .

(b)     (i)     Define an Eulerian circuit.

          (ii)     Write down an Eulerian circuit in G starting at P.

(c)     (i)     Define a Hamiltonian cycle.

         (ii)     Explain why it is not possible to have a Hamiltonian cycle in G .

Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T . Write down this shortest path.

(i)     Does this graph have an Eulerian circuit? Justify your answer.

(ii)     Does this graph have an Eulerian trail? Justify your answer.

The graph above is now to be considered with the edges representing roads in a town and with the distances being the length of that road in kilometres. Huan is a postman and he has to travel along every road in the town to deliver letters to all the houses in that road. He has to start at the sorting office at S and also finish his route at S . Find the shortest total distance of such a route. Fully explain the reasoning behind your answer.

Consider the following weighted graph.

(a)     (i)     Use Kruskal’s algorithm to find the minimum spanning tree. Indicate the order in which you select the edges and draw the final spanning tree.

  (ii)     Write down the total weight of this minimum spanning tree.

(b)     Sketch a spanning tree of maximum total weight and write down its weight.

The vertices of a graph L are A, B, C, D, E, F, G and H. The weights of the edges in L are given in the following table.

Draw the graph L.

In any graph, show that

(i)     the sum of the degrees of all the vertices is even;

(ii)     there is an even number of vertices of odd degree.

Consider the following graph, M.

(i)     Show that M is planar.

(ii)     Explain why M is not Eulerian.

(iii)     By adding one edge to M it is possible to make it Eulerian. State which edge must be added.

This new graph is called N.

(iv)     Starting at A, write down a possible Eulerian circuit for N.

(v)     Define a Hamiltonian cycle. If possible, write down a Hamiltonian cycle for N, and if not possible, give a reason.

(vi)     Write down the adjacency matrix for N.

(vii)     Which pair of distinct vertices has exactly 30 walks of length 4 between them?